﻿// 排序算法1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<string.h>
#include<stdio.h>
//冒泡排序
void BubbleSort(int arr[], int size)
{
    for (int i = 0; i < size-1; i++)
    {
        bool a = false;
        for (int j = 0; j < size-i-1; j++)//每趟元素需要做的调整步数
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                a = true;
            }

        }
        if (a !=true)
            break;//如果没发生交换，说明排序完成，打破循环。
    }
    //每趟元素遍历比较，大的下沉，小的上浮，循环，直至数组元素排序完成
    //下一趟较上一趟数量少1
    //优化：当后面有一次没有发生交换时，说明元素排序已经完成，可以结束排序
}
//选择排序
void ChoiceSort(int arr[], int size)
{
    //假定第一位元素是最小的，在后面元素选择最小的一个元素和它比较，比它小和它交换，
    //没它小换下一个元素重复之前操作    
    for (int i = 0; i < size-1; i++)
    {
        int min = arr[i];//假定arr[i]是最小的
        int num = i;//记录最小值的下标
        for (int j = i + 1; j < size; j++)//筛选后续元素中最小的
        {
            if (arr[j] < min)
            {
                min = arr[j];
                num =j;
               
            }
        }
        
        arr[num] = arr[i];//将小于arr[i]的最小值和arr[i]互换位置
        arr[i] = min;
    }
}
//插入排序
void InsertSort(int arr[], int size)
{
    //插入排序假定第一个元素是有序的，它在有序的元素排序时效率是最高的
    //其后元素在前面有序的元素中查找第一个小于该元素的元素，将其后的元素全部后移一位
    //将待排序的元素插入其后
    for (int i = 1; i < size ; i++)
    {
        int val=arr[i];
        int j = i - 1;
        for (; j >=0; j--)
        {
            if (arr[j] >= val)
            {
                arr[j+1] = arr[j];
            }
            else
                break;
        }
        arr[j + 1] = val;

    }
}
//希尔（shell）排序
void ShellSort(int arr[], int size)
{
    //在插入排序的基础上引入分组的概念，目的在于让杂乱无章的元素趋于有序化，最后在进行一次插入排序
    for (int gap = size / 2; gap > 0; gap /= 2)//分组的变化，gap既是分组数又是间隙数
    {
        for (int i = gap; i < size; i++)
        {
            int val = arr[i];
            int l;
            int j = i - gap;
            for (; j >= 0; j -= gap)
            {
                if (arr[j] >= val)
                {
                    arr[j + gap] = arr[j];
                }
                else
                    break;
            }
            arr[j + gap] = val;
        }
    }
}
int main()
{
    srand(time(0));
    int str, end;
    int* arr = (int*)malloc(sizeof(int) * 100000);
    int* brr = (int*)malloc(sizeof(int) * 100000);
    int* crr = (int*)malloc(sizeof(int) * 100000);
    int* drr = (int*)malloc(sizeof(int) * 100000);
    for (int i = 0; i < 100000; i++)
    {
        arr[i] = rand();
        brr[i] = rand();
        crr[i] = rand();
        drr[i] = rand();
    }

    str = clock();
    BubbleSort(arr, 100000);
    end = clock();
    printf("BubbleSort.time:%d ms", end - str);
    printf("\n");

    str = clock();
    ChoiceSort(brr, 100000);
    end = clock();
    printf("ChoiceSort.time:%d ms", end - str);
    printf("\n");


    str = clock();
    InsertSort(crr, 100000);
    end = clock();
    printf("InsertSort.time:%d ms", end - str);
    printf("\n");


    str = clock();
    ShellSort(drr, 100000);
    end = clock();
    printf("ShellSort.time:%d ms", end - str);
    printf("\n");


   
   }
/*
*   项目     最坏时间复杂度   最优时间复杂度   平均时间复杂度         空间复杂度    稳定性
* 冒泡排序    O（n^2)            O(n)             O(n^2)                 O(1)        稳定
* 选择排序    O（n^2)            O（n^2)          O（n^2)                O(1)       不稳定
* 插入排序    O（n^2)            O（n）           O（n^2)                O(1)        稳定
* 希尔排序    O（n^2)            O（n）        合适的gap，O（n^1.3)      O(1)       不稳定
*/
#if 0
    int arr[10] = { 0 };
    int brr[10] = { 0 };
    int crr[10] = { 0 };
    int drr[10] = { 0 };

    srand(time(0));
    for (int i = 0; i < 10; i++)
    {
        arr[i] = rand() % 100;
        brr[i] = rand() % 100;
        crr[i] = rand() % 100;
        drr[i] = rand() % 100;

    }
    BubbleSort(arr, 10);
    ChoiceSort(brr, 10);
    InsertSort(crr, 10);
    ShellSort(drr, 10);
    for (auto v : arr)
        printf("%d ", v);
    printf("\n");
    for (auto b : brr)
        printf("%d ", b);
    printf("\n");
    for (auto c : crr)
        printf("%d ", c);
    printf("\n");
    for (auto d : drr)
        printf("%d ", d);
    printf("\n");

}
#endif